1. Field of the Invention
The present invention relates to video compression and decompression. More specifically, the present invention relates to improved video compression/decompression using image preprocessing and vector quantization (VQ).
2. Background of Related Art
Modem applications, such as multimedia or other applications requiring full motion video required the development of video compression standards for reducing the processing bandwidth consumed by storing, transmitting, and displaying such video information. This is due to the large amount of data to transmit or store for representing high resolution full image video information. Generally, apparatus such as shown in FIGS. 1a, 1b, and 1c are employed in order to compress and decompress an input image for vector quantization based techniques. For instance, as shown in FIG. 1a, an image 100 may be input to an encoder 101 which applies spatial or temporal preprocessing to an input image or sequence of images in order to reduce the redundancy or otherwise reduce the amount of information contained in the input image 100. Encoder 101 generates a compressed image 102 which is substantially smaller than the original image 100. In certain prior art systems, the encoder 101 uses a codebook 105 which is used for matching given pixel patterns in the input images 100, so that the pixel patterns are mapped to alternative pixel patterns in the compressed images 102. In this manner, each area in the image may be addressed by referencing an element in the codebook by an index, instead of transmitting the particular color or other graphics information. Although in some prior art applications, quality is lost in compressed images 102, substantial savings are incurred by the reduction in the image size from images 100 to compressed images 102. Other compression techniques are "loss-less" wherein no quality in the decoded images is lost generally at the cost of additional computation time or a larger bitstream.
Conversely, compressed images 102 may be applied to a decoder 131, as shown in FIG. 1b, in order to generate decompressed images 132. Again, decoder 131 uses codebook 105 to determine the pixel patterns represented in images 132 from the indices contained within compressed images 102. Decoder 131 requires the use of the same codebook 105 which was used to encode the image. Generally, in prior art systems, the codebook is unique as associated with a given image or set of images which are compressed and/or decompressed for display in a computer system.
Generally, a codebook such as 105 is generated from image or training set of images 151 which is applied to a codebook generator 152. The codebook can be generated specifically from and for one or more images that are compressed, and that codebook is used for decoding the images it was generated from. The codebook can also be generated once by optimizing it for a long training sequence which is meant to be a reasonable representation of the statistics of sequences of images to be coded in the future. This training codebook is meant to be representative of a large range of image characteristics. The training codebook is often fixed at the encoder and decoder, but pieces of the codebook may also be improved adaptively. In some prior art schemes, codebook generator 152 and encoder 101 are one in the same. Encoding is performed simultaneous with codebook generation, and the codebook is derived from the encoded image(s) instead of training image(s).
FIG. 2 shows how an image 200 may be partitioned to discrete areas known as vectors for encoding and decoding of the image. In one prior art approach, an image such as 200 is divided into a series of 2.times.2 pixel blocks such as 201 and 202 which are known as "vectors." Each of the vectors such as 201 comprises four pixels 201a, 201b, 201c, and 201d. When an image has been broken down into such vectors, each of the vectors in the bitstream may be used to: (a) encode an image which may include generating a codebook; and (b) decode an image. Each of the vectors such as 201,202, etc. in image 200 may be used to represent image 200. Thus, an image may be represented by references to elements in a codebook which each are approximations of the vectors contained in the image. Thus, instead of representing the image by using four discrete pixels such as 201a through 201d, the image may be represented by referencing a codebook index which approximates information contained in vector 201. Depending on the number of entries in the codebook, using the codebook index to refer to an image vector can substantially reduce the storage required for representing the vector because the actual pixel values 201a-201d are not used to represent the image.
Such prior art apparatus, such as discussed with reference to FIGS. 1a through 1c, are implemented in a device known as a codec (coder/decoder) which generates a compressed bitstream for a sequence of images from the corresponding codebook, and uses the codebook to decompress the images at a later time. For example, such a codec is shown as apparatus 300 in FIG. 3. Codec 300 comprises two sections: encoder 301 and decoder 351. Encoder 301 accepts as input data 310, which may be video, sound, or other data which is desired to be compressed. For the purposes of the remainder of this application, a discussion of video encoding/decoding will ensue, however, it can be appreciated by one skilled in the art that similar schemes may be applied to other types of data. Such input data may be applied to a preprocessor 320 wherein certain parameters are adjusted to preprocess the data in order to make encoding/decoding an easier task. Preprocessor 320 then feeds into a vector quantizer 330 which uses vector quantization to encode the image in some manner, which equivalently reduces redundancies. Then, vector quantizer 330 outputs to a packing/coding process 340 to further compress the bitstream. A rate control mechanism 345 receives information about the size of the compressed bitstream 350, and various parameters are adjusted in preprocessor 320 in order to achieve the desired datarate. Moreover, preprocessor 320 samples the encoded data stream in order to adjust quality settings.
Codec 300 further includes a decoder 351 which receives and decodes the compressed bitstream 350 by using a codebook regenerator 360. The decoder in the encoder need not go through the packing 340 or unpacking 370 process in order to decode the image. In the decoder, codebook regenerator 360 is fed into an unpacking process 370 for restoring the full bitstream. The results of this process may be passed to a postfilter 375 and then dithering 380 may be performed upon the image, and finally the image is displayed, 390.
Examples of prior art vector quantization processes may be found in the reference: Gray, R. M., "Vector Quantization," 1IEEE ASSP Magazine,4-29 (April 1984) ("Gray"), and Nasrabadi, N. M., "Image Coding Using Vector Quantization: A Review, " COM-36IEEE Transaction on Communications,957-971 (August 1988) ("Nasrabadi"). Such vector quantization includes the creation of a tree searched vector quantizer which is described in Gray at pp.16-17, and in Nasrabadi at p.75.
The codebook generation process is iterative and tends to be computationally expensive. Thus, in some prior art methods, which require a codebook per frame, the encoding tends to be slow. Also, a drawback to prior art systems which use training sequences is quality, which may not be acceptable for many sequences which may not be similar to image(s) in the training sequence. Overall performance is also a concern. Some prior art techniques require an inordinate amount of processing and still do not achieve acceptable compression while not being able to perform the compression in real-time. Demands for fast decoding capability are often even more stringent or real time playback is not possible. Most prior art systems also have a computationally expensive decoder.